A Low Density Parity Check (LDPC) code has the high error correction capability and has been recently adopted widely to a transmission system including satellite digital broadcasting such as Digital Video Broadcasting (DVB)-S.2 performed in Europe (for example, refer to Non-Patent Document 1). In addition, adopting of the LDPC code to next-generation terrestrial digital broadcasting has been examined.
From a recent study, it is known that performance near a Shannon limit is obtained from the LDPC code when a code length increases, similar to a turbo code. In addition, because the LDPC code has a property that a shortest distance is proportional to the code length, the LDPC code has advantages of a block error probability characteristic being high and a so-called error floor phenomenon observed in a decoding characteristic of the turbo code or the like being rarely generated, as characteristics thereof.
Hereinafter, the LDPC code will be specifically described. The LDPC code is a linear code and it is not necessary for the LDPC code to be a binary code. However, here, it is assumed that the LDPC code is the binary code.
A maximum characteristic of the LDPC code is that a parity check matrix defining the LDPC code is sparse. Here, the sparse matrix is a matrix in which the number of “1” of elements of the matrix is very small (a matrix in which most elements are 0).
FIG. 1 illustrates an example of a parity check matrix H of the LDPC code.
In the parity check matrix H of FIG. 1, a weight of each column (the column weight) (the number of “1”) becomes “3” and a weight of each row (the row weight) becomes “6”.
In encoding using the LDPC code (LDPC encoding), for example, a generation matrix G is generated on the basis of the parity check matrix H and the generation matrix G is multiplied with binary information bits, so that a code word (LDPC code) is generated.
Specifically, an encoding device that performs the LDPC encoding first calculates the generation matrix G in which an expression GHT=0 is realized, between a transposed matrix HT of the parity check matrix H and the generation matrix G. Here, when the generation matrix G is a K×N matrix, the encoding device multiplies the generation matrix G with a bit string (vector u) of information bits consisting of K bits and generates a code word c (=uG) consisting of N bits. The code word (LDPC code) that is generated by the encoding device is received at a reception side through a predetermined communication channel.
The LDPC code can be decoded by an algorithm called probabilistic decoding suggested by Gallager, that is, a message passing algorithm using belief propagation on a so-called Tanner graph, consisting of a variable node (also referred to as a message node) and a check node. Here, the variable node and the check node are appropriately referred to as nodes simply hereinafter.
FIG. 2 illustrates a sequence of decoding of the LDPC code.
Hereinafter, a real value (reception LLR) that is obtained by representing the likelihood of “0” of a value of an i-th sign bit of the LDPC code (one code word) received by the reception side by a log likelihood ratio is appropriately referred to as a reception value u0i. In addition, a message output from the check node is referred to as uj and a message output from the variable node is referred to as vi.
First, in decoding of the LDPC code, as illustrated in FIG. 2, in step S11, the LDPC code is received, the message (check node message) uj is initialized to “0”, and a variable k taking an integer as a counter of repetition processing is initialized to “0”, and the processing proceeds to step S12. In step S12, the message (variable node message) vi is acquired by performing an operation (variable node operation) represented by an expression (1), on the basis of the reception value u0i obtained by receiving the LDPC code, and the message uj is acquired by performing an operation (check node operation) represented by an expression (2), on the basis of the message vi.
                    [                  Formula          ⁢                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              i                =                1                                                              d                  v                                -                1                                      ⁢                                                  ⁢                          u              j                                                          (        1        )                                [                  Formula          ⁢                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                                          ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Here, dv and dc in the expressions (1) and (2) represent parameters that show numbers of “1” of the parity check matrix H in a vertical direction (column) and a horizontal direction (row), respectively, and can be arbitrarily set, respectively. For example, in the case of a (3, 6) code, dv=3 and dc=6.
In the variable node operation of the expression (1) and the check node operation of the expression (2), because a message input from an edge (line connecting the variable node and the check node) for outputting the message is not an operation target, an operation range becomes 1 to dv−1 or 1 to dc−1. The check node operation of the expression (2) is performed actually by previously making a table of a function R (v1, v2) represented by an expression (3) defined by one output with respect to two inputs v1 and v2 and using the table consecutively (recursively), as represented by an expression (4).[Formula 3]X=˜2 tan−1[tan h(v1/2)tan h(v2/2)]=R(v1,v2)  (3)[Formula 4]uj=R(v1,R(v2,R(v3, . . . R(vd0−2,Vd0−1))))  (4)
In step S12, the variable k is incremented by “1” and the processing proceeds to step S13. In step S13, it is determined whether the variable k is more than the predetermined repeat decoding count C. When it is determined in step S13 that the variable k is not more than C, the processing returns to step S12 and the same processing is repeated hereinafter.
When it is determined in step S13 that the variable k is more than C, the processing proceeds to step S14, the message vi that corresponds to a decoding result to be finally output is acquired by performing an operation represented by an expression (5) and is output, and the decoding processing of the LDPC code ends.
                    [                  Formula          ⁢                                          ⁢          5                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                            d                y                                      ⁢                                                  ⁢                          u              j                                                          (        5        )            
Here, the operation of the expression (5) is performed using messages uj from all edges connected to the variable node, different from the variable node operation of the expression (1).
FIG. 3 illustrates an example of the parity check matrix H of the (3, 6) LDPC code (an encoding rate of 1/2 and a code length of 12).
In the parity check matrix H of FIG. 3, a weight of a column is set to 3 and a weight of a row is set to 6, similar to FIG. 1.
FIG. 4 illustrates a Tanner graph of the parity check matrix H of FIG. 3.
In FIG. 4, the check node is represented by plus “+” and the variable node is represented by equal “=”. The check node and the variable node correspond to the row and the column of the parity check matrix H. A line that connects the check node and the variable node is the edge and corresponds to “1” of elements of the parity check matrix.
That is, when an element of a j-th row and an i-th column of the parity check matrix is 1, in FIG. 4, an i-th variable node (node of “=”) from the upper side and a j-th check node (node of “+”) from the upper side are connected by the edge. The edge shows that a sign bit corresponding to the variable node has a restriction condition corresponding to the check node.
In a Sum Product Algorithm that is a decoding method of the LDPC code, the variable node operation and the check node operation are repetitively performed.
FIG. 5 illustrates the variable node operation that is performed by the variable node.
In the variable node, the message vi that corresponds to the edge for calculation is acquired by the variable node operation of the expression (1) using messages ul and u2 from the remaining edges connected to the variable node and the reception value u0i. The messages that correspond to the other edges are also acquired by the same method.
FIG. 6 illustrates the check node operation that is performed by the check node.
Here, the check node operation of the expression (2) can be rewritten by an expression (6) using a relation of an expression a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b). However, sign(x) is 1 in the case of x≧0 and is −1 in the case of x<0.
                    [                  Formula          ⁢                                          ⁢          6                ]                                                                                                                u                j                            =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                                                                          ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                0                                                            -                              1                                                                                ⁢                                                                                                          ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                  sign                          ⁡                                                      (                                                          tanh                              ⁡                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                                                                                          ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                                                          ⁢                                      sign                    (                                          v                      i                                        )                                                                                                          (        6        )            
In x≧0, if a function φ(x) is defined as an expression φ(x)=ln(tan h(x/2)), an expression φ−1(x)=2 tan h−1(e−x) is realized. For this reason, the expression (6) can be transformed into an expression (7).
                    [                  Formula          ⁢                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                                                  ⁢                          sign              ⁢                                                          ⁢                              (                                  v                  i                                )                                                                        (        7        )            
In the check node, the check node operation of the expression (2) is performed according to the expression (7).
That is, in the check node, as illustrated in FIG. 6, the message uj that corresponds to the edge for calculation is acquired by the check node operation of the expression (7) using messages v1, v2, v3, v4, and v5 from the remaining edges connected to the check node. The messages that correspond to the other edges are also acquired by the same method.
The function φ(x) of the expression (7) can be represented as an expression φ(x)=ln((ex+1)/(ex−1)) and φ(x)=φ−1(x) is satisfied in x>0. When the functions φ(x) and φ−1(x) are mounted to hardware, the functions φ(x) and φ−1(x) may be mounted using an Look Up Table (LUT). However, both the functions φ(x) and φ−1(x) become the same LUT.